package hot100;

import java.util.ArrayDeque;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/12 15:24
 */
public class lc239滑动窗口的最大值 {


    /*
     主要是单调队列的使用
     维持单调队列的单调性
     */


    public int[] solve(int nums[],int k){
//        int  r = nums.length;
        int ans[] = new int[nums.length - k + 1]; // 这是总共要收集的结果数

        ArrayDeque<Integer>  queue = new ArrayDeque<>();
        int r = 0,index = 0; // 固定窗口, l 直接不要了
        while(r < nums.length){


            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[r]){ // 入队列的时候需要判断
                queue.removeLast();
            }
            queue.addLast(r);

            if(queue.peekFirst() == r - k){ // r - k 表示 窗口内应该过期的下标, 如果过期的下标位置的值刚好是当前窗口内的最大值,那么直接丢掉
                queue.removeFirst();
            }
            if(r >= k - 1){// 只有这个时候, 才需要取收集答案
                ans[index++] = nums[queue.peekFirst()];
            }
            r++;
        }

        StringBuilder sb = new StringBuilder();
        return ans;
    }



}
